// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-21 00:16
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Hash;

import java.util.HashMap;
import java.util.Map;

@SuppressWarnings("ALL")
public class LFUCacheThird {
    /**
     * 桶排序 + Hash
     */

    /**
     * cache的空间
     */
    private int capacity, init;
    private Map<Integer, Bucket> map;
    /**
     * 因为使用的数据结构是链表嵌套链表，需要对链表的表头和表尾进行初始化，所以桶链表的表头和表尾就定义在类中，
     * 而真正存储数据的双向链表的表头和表尾则在桶链表中进行定义
     * 总结：
     * 当以内部类形式表现链表的时候，链表的表头和表尾需要在内部类之外进行初始化
     * 双向链表还应该对表头节点和表尾节点的关系进行初始化
     */
    Bucket bhh;
    Bucket btt;


    public LFUCacheThird(int capacity) {
        this.capacity = capacity;
        init = capacity;
        bhh = new Bucket(-1);
        btt = new Bucket(-1);
        map = new HashMap<Integer, Bucket>();
        bhh.r = btt;
        btt.l = bhh;
    }


    /**
     * 桶类，用于存储外面节点
     */
    class Bucket {
        int cnt;
        /**
         * 因为桶里存放的是Node节点的数据，所以定义一个Hash表实现对双向链表节点的快速索引
         */
        Map<Integer, Node> bucketMap = new HashMap<>();
        Bucket l, r;
        /**
         * 因为信息节点链表中存储的是信息，所以信息链表的头结点和尾节点设定为空节点
         */
        Node nhh;
        Node ntt;


        public Bucket(int cnt) {
            this.cnt = cnt;
            nhh = new Node(-1, -1);
            ntt = new Node(-1, -1);
            nhh.r = ntt;
            ntt.l = nhh;
        }


    }

    /**
     * 双向链表节点类。用于键值对的存取
     */
    class Node {
        int k, v;
        Node l, r;

        public Node(int k, int v) {
            this.k = k;
            this.v = v;
        }


    }

    /**
     * 清理空桶
     */
    void clear(Bucket bucket) {
        if (bucket == null) {
            return;
        }
        if (bucket.bucketMap.isEmpty()) {
            bucket.l.r = bucket.r;
            bucket.r.l = bucket.l;
        }
    }


    /**
     * 数据结构的取元素操作，取元素的时候从类中的hash表找到桶，然后再桶的hash表中找到存储信息的节点
     *
     * @param key
     * @return
     */
    public int get(int key) {
        if (map.containsKey(key)) {
            // 更新插入的值
            put(key, map.get(key).bucketMap.get(key).v);
            return map.get(key).bucketMap.get(key).v;
        } else {
            return -1;
        }
    }

    /**
     * 元素的添加操作
     * 结构中存在该元素：
     * 直接修改键对应的值，并且将存储信息的节点移动到正确的桶中，更新hash信息
     * 结构中不存在该元素：
     * 1 结构中空间足够：直接添加到正确的位置即可
     * 2 结构中的空间不足，需要移除最久未使用的元素，然后插入新元素
     *
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        if (init == 0) {
            return;
        }
        //  1 结构中存在该元素
        Bucket next = null;
        Node nextNode = null;
        if (map.containsKey(key)) {
            // 获取信息节点所在的桶位置
            Bucket bucket = map.get(key);
            // 从桶节点中获取存储信息的节点的位置
            Node node = bucket.bucketMap.get(key);
            // 将信息节点移动到正确位置
            if (bucket.r.cnt == bucket.cnt + 1) {
                next = bucket.r;

            } else {
                // 插入新桶
                next = new Bucket(bucket.cnt + 1);
                next.r = bucket.r;
                bucket.r.l = next;
                bucket.r = next;
                next.l = bucket;
            }
            node.r.l = node.l;
            node.l.r = node.r;

            // 将获取的节点放入正确的位置
            node.l = next.ntt.l;
            node.r = next.ntt;
            next.ntt.l.r = node;
            next.ntt.l = node;
            node.v = value;
            bucket.bucketMap.remove(key);
            // 虽然node节点从hash表中删除了，但是并没有在链表是对node节点进行删除

            clear(bucket);
            next.bucketMap.put(key, node);
            map.put(key, next);
        } else {
            // 结构中不存在该元素-> 直接创建节点值，并且放入合适的桶内
            // 如果结构空间不足，则需要将LFU元素移除
            if (capacity <= 0) {
                // 结构空间不足,需要移除LFU元素,获取待删除的节点
                Node node = bhh.r.nhh.r;
                // 待删除的键值
                int k = node.k;
                node.r.l = node.l;
                node.l.r = node.r;
                bhh.r.bucketMap.remove(k);
                map.remove(k);
                clear(bhh.r);
            }


            Node node = new Node(key, value);
            if (bhh.r.cnt == 1) {
                // 存在合适的桶
                next = bhh.r;
            } else {
                // 不存在合适的桶，直接创建合适的桶，并将元素放进桶内
                next = new Bucket(1);
                next.r = bhh.r;
                next.l = bhh;
                bhh.r.l = next;
                bhh.r = next;
            }

            // 把后面放入的元素放在链表后面，这样后面删除LFU值的时候直接从表头取出即可
            node.l = next.ntt.l;
            node.r = next.ntt;
            next.ntt.l.r = node;
            next.ntt.l = node;
            // 将信息放入合适的桶内
            next.bucketMap.put(key, node);
            map.put(key, next);
            capacity--;
        }
    }


    public static void main(String[] args) {
        LFUCacheThird lf = new LFUCacheThird(2);
        lf.put(1, 1);
        lf.put(2, 2);
        System.out.println(lf.get(1));
        lf.put(3, 3);
        System.out.println(lf.get(2));
        System.out.println(lf.get(3));
        lf.put(4, 4);
        System.out.println(lf.get(1));
        System.out.println(lf.get(3));
        System.out.println(lf.get(4));

    }
}
